import random


class Sort:
    def __init__(self, arr_len):
        self.arr = []
        self.arr_len = arr_len

    def random_list(self):
        for i in range(self.arr_len):
            self.arr.append(random.randint(0, 99))

    def bubble(self):
        arr = self.arr
        i = self.arr_len - 1
        while i > 0:
            j = 0
            flag = 1
            while j < i:
                if arr[j] > arr[j + 1]:  # 把最小的换到开头
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 冒泡比小一次换一次
                flag = 0
                j += 1
            if flag:
                break
            i -= 1

    def select(self):
        arr = self.arr
        for i in range(self.arr_len - 1):
            min_pos = i
            for j in range(i + 1, self.arr_len):
                if arr[j] < arr[min_pos]:  # 从小到大排序
                    min_pos = j
            arr[i], arr[min_pos] = arr[min_pos], arr[i]  # 比冒泡少交换，这个比一轮只换一次

    def insert(self):
        arr = self.arr
        i = 1
        while i < self.arr_len:
            insertVar = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > insertVar:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = insertVar
            i += 1

    # 王道方法快排
    def partition(self, left, right):
        arr = self.arr
        pivot = left
        while left < right:
            if arr[pivot] < arr[right]:
                right -= 1
            else:
                arr[pivot], arr[right] = arr[right], arr[pivot]
            if arr[pivot] > arr[left]:
                left += 1
            else:
                arr[pivot], arr[left] = arr[left], arr[pivot]
        return pivot

    def quick(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick(left, pivot - 1)
            self.quick(pivot + 1, right)


if __name__ == '__main__':
    # 建列表
    temp = Sort(10)
    temp.random_list()
    print(temp.arr)

    # 冒泡排序测验
    # temp.bubble()
    # print(temp.arr)

    # 选择排序测验
    # temp.select()
    # print(temp.arr)

    # 插入排序测试
    # temp.insert()
    # print(temp.arr)

    # 快速排序测试
    temp.quick(0, temp.arr_len - 1)
    print(temp.arr)
